﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder)
    {
        int preOrderLeft = 0,
            preOrderRight = preorder.Length - 1,
            inOrderLeft = 0,
            inOrderRight = inorder.Length - 1;
            
        return CreateBinaryTree(preorder, preOrderLeft, preOrderRight, inorder, inOrderLeft, inOrderRight);
    }

    private TreeNode CreateBinaryTree(int[] preorder, int preOrderLeft, int preOrderRight, int[] inorder, int inOrderLeft, int inOrderRight)
    {
        if (inOrderLeft > inOrderRight || preOrderLeft > preOrderRight) return null;
        int nodeVal = preorder[preOrderLeft];
        TreeNode node = new TreeNode(nodeVal);
        
        int inOrderMid = inOrderLeft;
        for (; inOrderMid <= inOrderRight; inOrderMid++)
        {
            if (inorder[inOrderMid] == nodeVal) break;
        }

        if (inOrderMid > inOrderRight)
        {
            Console.WriteLine("输入数据不符合规范！");
            return null;
        }

        int left_inOrderLeft = inOrderLeft;
        int left_inOrderRight = inOrderMid - 1;
        int left_preOrderLeft = preOrderLeft + 1;
        int left_preOrderRight = left_preOrderLeft + left_inOrderRight - left_inOrderLeft;
        node.left = CreateBinaryTree(preorder, left_preOrderLeft, left_preOrderRight, inorder, left_inOrderLeft, left_inOrderRight);
        
        int right_inOrderLeft = inOrderMid + 1;
        int right_inOrderRight = inOrderRight;
        int right_preOrderRight = preOrderRight;
        int right_preOrderLeft = right_preOrderRight - right_inOrderRight + right_inOrderLeft;
        node.right = CreateBinaryTree(preorder, right_preOrderLeft, right_preOrderRight, inorder, right_inOrderLeft, right_inOrderRight);
        return node;
    }

    public static void Main(string[] args)
    {
        int[] preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7];
        
        Solution solution = new Solution();
        TreeNode rootNode = solution.BuildTree(preorder, inorder);
        
        // 前序遍历
        PreOrderPrint(rootNode);
    }

    private static void PreOrderPrint(TreeNode rootNode)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (rootNode is not null) stack.Push(rootNode);
        TreeNode node;
        while (stack.Count > 0)
        {
            node = stack.Pop();
            Console.Write($"{node.val} ");
            if (node.right is not null) stack.Push(node.right);
            if (node.left is not null) stack.Push(node.left);
        }
    }
}